#include <stdio.h>
#define M 1000003
int main()
{
    int n, m, i;
    int x[1001];
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        x[1]=m;
        x[2]=m*(m-1)%1000003;
        x[3]=m*(m-1)*(m-2)%1000003;
        if( n > 3)
        {
            for(i=4;i<=n;i++)
            {
                x[i]= (x[i-1]*(m-2)+x[i-2]*(m-1))%1000003;
            }
        }
        printf("%d\n",x[n]);
    }

}
